<!--
 * @Descripttion: 
 * @version: 
 * @Author: 尹鹏孝
 * @Date: 2021-12-20 09:53:47
 * @LastEditors: 尹鹏孝
 * @LastEditTime: 2021-12-20 10:21:17
-->
<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>求左叶子节点和</title>
</head>

<body>
    <script>
        // 左叶子的明确定义,如果左节点不为空，且左节点没有左右孩子，那么这个节点就是左叶子
        // 思路，那么判断当前节点是不是左叶子是无法判断的，必须要通过节点的父节点来判断其左孩子是不是左叶子。如果该节点的左节点不为空，该节点的左节点的左节点为空，该节点的左节点的右节点为空，则找到了一个左叶子。

        // 1、递归法，后序遍历（左右中），是因为要通过递归函数的返回值来累加求取左叶子的数值和。
        // 1）判断入参和返回值，
        // 判断一个树的左叶子节点之和，那么先传入树的根节点，递归函数的返回值为数值之和所以为init,使用函数即可
        // 2）确定终止条件
        // 如果节点是nUll则返回0；
        // 3）每个详细的单个递归的逻辑
        // 当遇到左侧叶子节点的时候，记录数值，然后通过递归求取左子树左叶子之和，相加便是整个树的左叶子之和
        /**
         * @name: sumOfLeftLeaves
         * @msg: 递归法求左叶子之和
         * @param {NodeTree} root
         * @return {Number} result
         */
        var sumOfLeftLeaves = function (root) {
            // 采用后序遍历，左右中，
            // 递归三部曲
            // 1、确认入参，和返回值
            const nodeSums = function (node) {
                // 2、确定终止条件
                if (node === null) {
                    return 0;
                }
                let leftValue = sumOfLeftLeaves(node.left);
                let rightValue = sumOfLeftLeaves(node.right);
                // 3、单层递归逻辑
                let midValue = 0;
                if (node.left && node.left.left === null && node.left.right === null) {
                    midValue = node.left.val;
                }
                let sum = midValue + leftValue + rightValue;
                return sum;
            }
            return nodeSums(root);
        }


        // 迭代法
        var sumOfLeftLeaves = function (root) {
            // 采用层序遍历
            if (root == null) {
                return null;
            }
            let queue = [];
            let sum = 0;
            queue.push(root);
            while (queue.length) {
                let node = queue.shift();
                if (node.left != null && node.left.left === null && node.left.right === null) {
                    sum += node.left.val;
                }
                node.left && queue.push(node.left);
                node.right && queue.push(node.right);

            }
            return sum;

        }

    </script>

</body>

</html>